package class09;

import java.util.ArrayList;

/**
 * @author zhangchaoliang
 * create 2022
 */
public class MaxSubBSTHead {
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data){
            value = data;
        }
    }

    public static int getBSTSize(Node head){
        if (head == null)
            return 0;
        ArrayList<Node> arr = new ArrayList<>();
        in(head,arr);
        for (int i=1;i<arr.size();i++){
            if (arr.get(i).value <= arr.get(i-1).value)
                return 0;
        }
        return arr.size();
    }

    public static void in(Node head,ArrayList<Node> arr){
        if (head == null)
            return;
        in(head.left,arr);
        arr.add(head);
        in(head.right,arr);
    }

    public static Node maxSubBSTHead1(Node head){
        if (head==null)
            return null;
        if (getBSTSize(head)!=0)
            return head;
        Node leftAns = maxSubBSTHead1(head.left);
        Node rightAns = maxSubBSTHead1(head.right);
        return getBSTSize(leftAns) >= getBSTSize(rightAns)?
                leftAns:rightAns;
    }

    public static class Info{
        public Node maxSubBSTHead;
        public int maxSubBSTSize;
        public int min;
        public int max;

        public Info(Node h,int size,int mi ,int ma){
            maxSubBSTHead = h;
            maxSubBSTSize = size;
            min = mi;
            max = ma;
        }
    }

    public static Node maxSubBSTHead2(Node head){
        if (head == null)
            return null;
        return process(head).maxSubBSTHead;
    }

    public static Info process(Node x){
        if (x == null)
            return null;
        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);
        int min = x.value;
        int max = x.value;
        Node maxSubBSTHead = null;
        int maxSubBSTSize = 0;
        if (leftInfo!=null){
            min = Math.min(min,leftInfo.min);
            max = Math.max(max,leftInfo.max);
            maxSubBSTHead = leftInfo.maxSubBSTHead;
            maxSubBSTSize = leftInfo.maxSubBSTSize;
        }
        if (rightInfo!=null){
            min = Math.min(min,rightInfo.min);
            max = Math.max(max,rightInfo.max);
            if (rightInfo.maxSubBSTSize > maxSubBSTSize){
                maxSubBSTHead = rightInfo.maxSubBSTHead;
                maxSubBSTSize = rightInfo.maxSubBSTSize;
            }
        }
        if (
                (leftInfo==null?true:
                        (leftInfo.maxSubBSTHead==x.left &&
                        leftInfo.max<x.value))
                        &&
                        (rightInfo==null?true:
                                (rightInfo.maxSubBSTHead== maxSubBSTHead.right
                                &&rightInfo.min >x.value
                                ))
        ){
            maxSubBSTHead=x;
            maxSubBSTSize = (leftInfo==null?0: leftInfo.maxSubBSTSize) +
                    (rightInfo==null?0: rightInfo.maxSubBSTSize);
        }
        return new Info(maxSubBSTHead,maxSubBSTSize,min,max);
    }
}
